package com.jhxy.algorithm.majorityelement;

/**
 * Date: 2024/3/10 16:43
 * Author: T_log
 * Description: 多数元素_消元法
 */
public class DelEleSolution {


    public int majorityElement(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }

        int i = 0;
        int j = 1;

        while (true) {
            //nums长度为2的时候准备的
            if (j == nums.length - 1) {
                break;
            }
            if (nums[i] == nums[j]) {
                j++;
            } else {
                //2,2,3,3,3,4,4,2,2,1
                nums[i] = Integer.MIN_VALUE;
                nums[j] = Integer.MIN_VALUE;
                //移动i至第一个非无效数
                while (nums[i] == Integer.MIN_VALUE) {
                    i++;
                    if (i == nums.length - 1) {
                        return nums[i];
                    }
                }

                //移动j至第一个非无效数
                while (nums[j] == Integer.MIN_VALUE || j <= i) {
                    j++;
                    if (j == nums.length - 1) {
                        return nums[i];
                    }
                }
            }
        }

        return nums[i];
    }
}
